HyperLib 1997 Winter - Disc 1/HYPERLIB-1997-Winter-CD1.ISO.7z/HYPERLIB-1997-Winter-CD1.ISO/オンラインウェア/UTIL/PL 2.0 SupplementDoc Folder.sit/PL 2.0 SupplementDoc Folder/Documentation/Appendix B. Generators and G…

Text File | 1995-03-23 | 8KB | 196 lines

Common Lisp the Language, 2nd Edition
-------------------------------------------------------------------------------

Appendix B.

By Crispin Perdue and Richard C. Waters

[change_begin]
PREFACE: Generators and gatherers are yet another approach, closely related to
series, to providing iteration in a functional style.

The remainder of this chapter consists of a description by Crispin Perdue and
Richard C. Waters of their work on an existing implementation of generators and
gatherers. I have edited the chapter only very lightly to conform to the
overall style of this book. Please see the Preface to this book for more
information about the genesis of the generators/gatherers approach and its
relationship to the work of X3J13.

     -Guy L. Steele Jr.

[change_end]
-------------------------------------------------------------------------------

   *  Introduction
   *  Generators
   *  Gatherers
   *  Discussion

-------------------------------------------------------------------------------

B.1. Introduction

[change_begin]
Generators are generalized input streams in the sense of Smalltalk [20]. A
generator can produce a potentially unbounded number of elements of any type.
Individual elements are not computed until requested by next-in. When an
element is taken from a generator, it is removed by side effect. Subsequent
uses of next-in obtain later elements.

There is a close relationship between a generator and a series of the elements
it produces. In particular, any series can be converted into a generator. As a
result, all the scanner functions used for creating series (see appendix A) can
be used to create generators as well. There is no need to have a separate set
of functions for creating generators.

Gatherers are generalized output streams. Elements of any type can be entered
into a gatherer using next-out. The gatherer combines the elements together in
time-sequence order into a net result. This result can be retrieved using
result-of.

There is a close relationship between a gatherer and a collector function that
combines elements in the same way. In particular, any one-input one-output
collector can be converted into a gatherer. As a result, all the collectors
used for computing summary results from series can be used to create gatherers.
There is no need to have a separate set of functions for creating gatherers.
[change_end]

-------------------------------------------------------------------------------

B.2. Generators

[change_begin]
These functions create and process generators.

[Function]
generator series

Given a series, generator returns a generator containing the same elements.

[Macro]
next-in generator {action}*

next-in returns the next element in the generator generator. The actions can be
any Lisp expressions. They are evaluated if and only if no more elements can be
retrieved from generator. If there are no more elements and no actions, it is
an error. It is also an error to apply next-in to a generator a second time
after the generator has run out of elements. As an example of generators,
consider the following.

(let ((x (generator (scan '(1 2 3 4)))))
  (with-output-to-string (s)
    (loop (prin1 (next-in x (return)) s)
          (prin1 (next-in x (return)) s)
          (princ "," s))))
 => "12,34,"

[change_end]

-------------------------------------------------------------------------------

B.3. Gatherers

[change_begin]
These functions create and process gatherers.

[Function]
gatherer collector

The collector must be a function of type (function ((series   ))   ). Given
this function, gatherer returns a gatherer that accepts elements of type    and
returns a final result of type   . The method for combining elements used by
the gatherer is the same as the one used by the collector.

[Function]
next-out gatherer item

Given a gatherer and a value, next-out enters the value into the gatherer.

[Function]
result-of gatherer

result-of retrieves the net result from a gatherer. result-of can be applied at
any time. However, it is an error to apply result-of twice to the same gatherer
or to apply next-out to a gatherer once result-of has been applied.

(let ((g (gatherer #'collect-sum)))
  (dolist (i '(1 2 3 4))
    (next-out g i)
    (if (evenp i) (next-out g (* 10 i))))
  (result-of g))
 => 70

[Macro]
gathering ({(var fn)}*) {form}*

The first subform must be a list of pairs. The first element of each pair, var,
must be a variable name. The second element of each pair, fn, must be a form
that when wrapped in (function ...) is acceptable as an argument to gatherer.
Each symbol is bound to a gatherer constructed from the corresponding
collector. The body (consisting of the forms) is evaluated in the scope of
these bindings. When this evaluation is complete, gathering returns the
result-of each gatherer. If there are n pairs in the binding list, gathering
returns n values. For example:

(defun examp (data)
  (gathering ((x collect) (y collect-sum))
    (iterate ((i (scan data)))
      (case (first i)
        (:slot (next-out x (second i)))
        (:part (dolist (j (second i)) (next-out x j))))
      (next-out y (third i)))))

(examp '((:slot a 10) (:part (c d) 40))) => (a c d) and 50

As a further illustration of gatherers, consider the following definition for a
simplified version of gathering that handles only one binding pair.

(defmacro simple-gathering (((var collector)) &body body)
  `(let ((,var (gatherer (function ,collector))))
     ,@body
     (result-of ,var)))

The full capabilities of gathering can be supported in much the same way.
[change_end]

-------------------------------------------------------------------------------

B.4. Discussion

[change_begin]
The idea of generators and gatherers was first proposed by Pavel Curtis. A key
aspect of his proposal was the realization that generators and gatherers can be
implemented simply and elegantly as closures and that these closures can be
compiled very efficiently if certain conditions are met.

First, the compiler must support an optimization Curtis calls ``let eversion''
in addition to the optimization methods presented in [45]. If a closure is
created and used entirely within a limited lexical scope, the scopes of any
bound variables nested in the closure can be enlarged (everted) to enclose all
the uses of the closure. This allows the variables to be allocated on the stack
rather than the heap.

Second, for a generator/gatherer closure to be compiled efficiently, it must be
possible to determine at compile time exactly what closure is involved and
exactly what the scope of use of the closure is. There are several aspects to
this. The expression creating the generator/gatherer cannot refer to a free
series variable. The generator/gatherer must be stored in a local variable.
This variable must be used only in calls of next-in, next-out, and result-of,
and not inside a closure. In particular the generator/gatherer cannot be stored
in a data structure, stored in a special variable, or returned as a result
value.

All of the examples above satisfy these restrictions. For instance, once the
uses of gathering and iterate have been optimized, the body of examp is as
efficient as any loop performing the same computation.

The implementation discussed in [52] includes a portable Common Lisp
implementation of generators and gatherers. Although the implementation does
not support optimizations of the kind discussed in [45], it fully optimizes
uses of gathering.
[change_end]

-------------------------------------------------------------------------------